#include<iostream>
#include<vector>

using namespace std;



class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0);
        return res;
    }

    // 回溯代码框架
    // 路径：board 中row 行及以上都放了皇后
    // 选择列表：row 行所有列都是选项
    // 结束条件： 放满了
    void backtrack(vector<string>& board, int row){
        // 触发结束, row 增大
        if(row == board.size()){
            res.push_back(board);
            return;
        }
        int n = board[row].size();
        for(int col = 0; col < n; col++){
            // 排除、跳过不合法选择
            if(!is_valid(board, row, col)){
                continue;
            }

            // 做选择
            board[row][col] = 'Q';
            backtrack(board, row + 1);
            //取消选择；
            board[row][col] = '.';
        }
        
    }

    // 是否可以在board[row][col] 放置皇后？
    bool is_valid(vector<string>& board, int row, int col){
        int n = board.size();

        // 检查列中是否有冲突
        for(int i = 0; i < row; i++){
            if(board[i][col] == 'Q')
                return false;
        }

        // 检查左上是否冲突
        for(int i = row -1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] == 'Q')
                return false;
        }

        // 检查右上是否冲突
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(board[i][j] == 'Q')
                return false;
        }
        // 正下、左下、右下不用检查

        return true;

    }
};

void print(vector<vector<string>> input){
    for(auto row : input){
        for(auto col : row){
            cout<<col<<" ";
        }
        cout<<endl;
    }
        

}
void test_01(){
    Solution slu;
    vector<vector<string>> ret = slu.solveNQueens(4);
    
    assert(ret.size() == 2);

    print(ret);
}

void test_02(){
    Solution slu;
    vector<vector<string>> ret = slu.solveNQueens(5);
    
    assert(ret.size() == 10);

    print(ret);
}

int main(){
    test_02();

    return 0;
}
